package com.yang.String_;

public class LeetCode28 {
    public static void main(String[] args) {
        String haystack = "hello", needle = "ll";
        SolutionLeetCode28 solutionLeetCode28 = new SolutionLeetCode28();
        int i1 = solutionLeetCode28.strStr(haystack, needle);
            System.out.println(i1);

    }
}

class SolutionLeetCode28 {
    public int strStr(String haystack, String needle) {
        if ( needle.length()==0 ){
            return 0;
        }
        int[] next = new int[needle.length()];
        next(next, needle);
        // 根据J在前缀表中就是-1开始
        int j = -1;
        for (int i = 0; i < haystack.length(); i++) {
            while( j>=0 && (haystack.charAt(i) != needle.charAt(j+1))){
                // 返回前一个最长相等前缀处
                j = next[j];
            }
            if (haystack.charAt(i) == needle.charAt(j+1)){
                j++;
            }
            // 当到模式串的末尾 则说明以及完成匹配
            if(j == needle.length()-1){
                return i - needle.length() + 1;
            }
        }
        return -1;
    }

    private void next(int[] next, String s){
        // 初始化next数组
        int j = -1;
        next[0] = j;
        for (int i = 1; i < s.length(); i++) {
            // 一直循环知道j跳到相等的前后缀处 最多跳到0
            while(j >= 0 && s.charAt(i) != s.charAt(j+1)){
                // 当遇到不相同的就往(最近相同前缀)回跳一次
                j = next[j];
            }
            // 如果相同就继续往前比较
            if( s.charAt(i) == s.charAt(j+1)) {
                j++;
            }
            // 前缀表记录当前最长相同前后缀长度
            next[i] = j;
        }
    }
}
